package sort.leetcode;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 215. 数组中的第K个最大元素
 */
public class FindKthLargest {
    /**
     * 优先级队列
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargestProQue(int[] nums, int k) {
        Queue<Integer> queue = new PriorityQueue<>();
        for (int num : nums) {
            if (queue.size() < k) {
                queue.offer(num);
            } else {
                if (num > queue.peek()) {
                    queue.poll();
                    queue.offer(num);
                }
            }
        }
        return queue.peek();
    }

    /**
     * 快速排序
     * @param nums
     * @param k
     * @return
     */
    public static int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        quickSort(nums, 0, len - 1, k, len);
        return nums[len - k];
    }

    private static void quickSort(int[] nums, int left, int right, int k, int len) {
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(right);
        stack.push(left);
        while (!stack.isEmpty()) {
            int l = stack.pop();
            int r = stack.pop();
            if (r - l <= 0) {
                continue;
            }
            int indexP = partition(nums, l, r);
            if (indexP == len - k) {
                return;
            }
            stack.push(r);
            stack.push(indexP + 1);
            stack.push(indexP - 1);
            stack.push(l);
        }
    }

    private static int partition(int[] nums, int l, int r) {
        int p = nums[l];
        int i = l;
        int j = r;
        while (i < j) {
            while (i < j && nums[j] >= p) {
                j --;
            }
            nums[i] = nums[j];
            while (i < j && nums[i] <= p) {
                i ++;
            }
            nums[j] = nums[i];
        }
        nums[i] = p;
        return i;
    }

    public static void main(String[] args) {
        int[] nums = new int[] {3, 2, 1, 5, 6, 4};
        System.out.println(findKthLargest(nums, 2));
    }
}
